package com.zhn;

import java.util.*;

/**
 * 给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
 *
 *
 *
 * 示例 1:
 *
 * 输入: nums = [1,1,1,2,2,3], k = 2
 * 输出: [1,2]
 * 示例 2:
 *
 * 输入: nums = [1], k = 1
 * 输出: [1]
 *
 *
 * 提示：
 *
 * 1 <= nums.length <= 105
 * k 的取值范围是 [1, 数组中不相同的元素的个数]
 * 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的
 *
 *
 * 进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。
 */

public class TopKFrequent {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            //Map.getOrDefault(Object key, V defaultValue);
            //如果在Map中存在key，则返回key所对应的的value。
            //如果在Map中不存在key，则返回默认值。
            map.put(nums[i], map.getOrDefault(nums[i],0)+1);
        }
//        PriorityQueue<Integer> priorityQue = new PriorityQueue<>(new Comparator<Integer>() {
//            @Override
//            public int compare(Integer a, Integer b) {
//                return map.get(a)-map.get(b);
//            }
//        });
        //Lambda写法
        //优先级队列对频率进行排序
        PriorityQueue<Integer> priorityQue = new PriorityQueue<>((a,b) ->{
                return map.get(a)-map.get(b);
        });
        for(Integer key: map.keySet()){
            if(priorityQue.size() < k){
                priorityQue.add(key);
        //Java中的java.util.PriorityQueue.peek()方法用于检索或获取Queue的第一个元素或出现在Queue头的元素。检索到的元素不会从队列中删除或删除。
            }else if(map.get(key) > map.get(priorityQue.peek())){
                priorityQue.remove();
                priorityQue.add(key);
            }
        }
        //取出最小堆中元素
        int count = 0;
        int[] res = new int[priorityQue.size()];
        while(!priorityQue.isEmpty()){
            res[count++] = priorityQue.remove();
        }
        return res;
    }
}
